package algorithm.swordoff;

/**
 * 在排序数组中查找数字
 * 本题与主站 34 题相同（仅返回值不同）
 * 二分法
 */

public class SQ53_1 {

    public int search(int[] nums, int target) {
        if (nums.length == 0 || nums[0] > target || nums[nums.length-1] < target) return 0;

        int headLow = 0, headHigh = nums.length-1;
        int tailLow = 0, tailHigh = nums.length-1;

        while (headLow < headHigh || tailLow < tailHigh) {

            if (headLow < headHigh) {
                int headMid = ((headHigh-headLow)>>1) + headLow;
                if (nums[headMid] < target) headLow = headMid+1;
                else headHigh = headMid;
            }

            if (tailLow < tailHigh) {
                // 下面这行是本题最难的地方
                int tailMid = ((tailHigh-tailLow+1)>>1) + tailLow;
                if (nums[tailMid] > target) tailHigh = tailMid-1;
                else tailLow = tailMid;
            }
        }

        return tailLow >= headLow ? tailLow-headLow+1 : 0;
    }
}
